package j2024.j202411;

public class j1122 {
    /**
     * 74. 搜索二维矩阵
     *
     * 给你一个满足下述两条属性的 m x n 整数矩阵：
     *
     * 每行中的整数从左到右按非严格递增顺序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length,n = matrix[0].length;
        int left = 0,right = m*n-1;
        while(left<=right){
            int mid = (right-left)/2+left;
            int tmp = matrix[mid/n][mid%n];
            if(tmp==target){
                return true;
            }
            if(tmp<target){
                left = mid+1;
            }else if(tmp>target){
                right = mid-1;
            }
        }
        return false;
    }

    /**
     * 162. 寻找峰值
     *峰值元素是指其值严格大于左右相邻值的元素。
     *
     * 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     *
     * 你可以假设 nums[-1] = nums[n] = -∞ 。
     *
     * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        int left = 0,right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid]>nums[mid+1]){
                right = mid;
            }else if(nums[mid] < nums[mid+1]){
                left = mid+1;
            }
        }
        return left;
    }
}
